package com.cd.algorithm.leetcode;

import org.junit.jupiter.api.Test;

/**
 * 寻找两个有序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n))
 * 例：
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 */
public class Topic4SoHard {
    @Test
    public void test() {
        int[] nums1 = new int[]{0,0,1};
        int[] nums2 = new int[]{3, 4};
        System.out.println(findMedianSortedArrays(nums1, nums2));
        System.out.println(myTest(nums1, nums2));
    }

    public double myTest(int[] nums1, int[] nums2) {
        //哪个数组长度小哪个是nums1
        if (nums2.length < nums1.length) {
            int[] temp = nums2;
            nums2 = nums1;
            nums1 = temp;
        }
        int totalLeft = (nums1.length + nums2.length+1) /2;
        //定义初始化
        int firstIndex = 0;
        int sencodeIndex = totalLeft - firstIndex;

        for (int i = 1; i<= totalLeft;i++){
            if(nums1[firstIndex] < nums2[sencodeIndex]){
                if(firstIndex == nums1.length -1){
                    sencodeIndex++;
                }else {
                    firstIndex++;
                }
            }else {
                if(sencodeIndex == nums2.length -1){
                    firstIndex++;
                }else {
                    sencodeIndex++;
                }
            }
        }

        int i = firstIndex;
        int j = sencodeIndex;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == nums1.length ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == nums2.length ? Integer.MAX_VALUE : nums2[j];

        if ((nums1.length + nums2.length) % 2 == 1) {
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            return (double) (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
        }

    }


    //二分查找法
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //哪个数组长度小哪个是nums1
        if (nums2.length < nums1.length) {
            int[] temp = nums2;
            nums2 = nums1;
            nums1 = temp;
        }
        int m = nums1.length;
        int n = nums2.length;
        //两个数组的下标
        int left = 0;
        int right = m;
        // 二分线左边总数，总数为偶数时例如4，下式结果为2，总数为奇数时例如5下式结果为3，总数为偶数时取左边最大和右边最小，总数为偶数时取左边最
        int totalLeft = (m + n + 1) / 2;
        //二分线左边的数量比右边的数量多1     5   3
        while (left < right) {
            //第一个数组的下标  第一个数组的长度减 第一个数组当前的下标 除以二
            int i = left + (right - left + 1) / 2;
            //第二个数组的下标
            int j = totalLeft - i;
            if (nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                left = i;
            }
        }
        int i = left;
        int j = totalLeft - i;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        if ((m + n) % 2 == 1) {
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            return (double) (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
        }
    }

}
